package twobranchTree.postorderTraversal;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/2/14
 * @author 王光浩
 * @Description 给出一颗二叉树，对该二叉树进行后序遍历。
 * @Thinking 使用迭代进行。核心思想：如果栈顶的节点和下一个栈顶的节点相同，则表示该节点需要加入到结果集中
 */
public class MyMethodThree {
	public List<Integer> postorderTraversal(TreeNode root){
		List<Integer> ret = new ArrayList<Integer>();
		if (root == null)
			return ret;
		Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
		stack.push(root);
		while ( !stack.isEmpty()) {
			TreeNode node = stack.poll();
			//node 和 栈顶节点相同，则将 node.val 加入到 ret 中
			if ( !stack.isEmpty() && stack.peek() == node) {
				stack.poll();
				ret.add(node.val);
				continue;
			}
			//如果不同
			stack.push(node);
			stack.push(node);
			if (node.right != null)
				stack.push(node.right);
			if (node.left != null)
				stack.push(node.left);
		}
		return ret;
	}
}
